let num = [2, 4, 1, 5, 7, 6, 9, 8];
// 选择排序
// 在未排序的数组元素中找到最小的数，把未排序的数组开头的位置的元素与最小的元素交换
function xuanZe(num) {
  let nin = 0;
  for (let i = 0; i < num.length - 1; i++) {
    min = num[i];
    for (let j = i + 1; j <= num.length - 1; j++) {
      if (num[min] > num[j]) {
        min = j;
      }
    }
    swap(min, j, num);
  }
}

function swap(min, i, num) {
  let temp = num[nim];
  num[min] = num[i];
  num[i] = temp;
}

num = [2, 4, 1, 5, 7, 6, 9, 8];
// 插入排序
// 每次选择一个未排序的元素，到之前排好序的元素比较，后插入到适当的地方
function cha(num) {
  for (let i = 1; i < num.length; i++) {
    let j = i;
    while (a[j] < a[j - 1]) {
      swap(j, j - 1, num);
      j--;
      if (j == 0) {
        break;
      }
    }
  }
}

num = [2, 4, 1, 5, 7, 6, 9, 8];
// 冒泡排序
// 两两比较，最终将大的元素都推到后面去。
function bubble(num) {
  for (let j = num.length - 1; j > 0; j--) {
    // 循环的总次数length-2,j表示此次冒泡排好序的位置；
    let swaped = false;
    for (let i = 0; i < j; i++) {
      if (num[i] > num[i + 1]) {
        swap(i, i + 1, num);
        swaped = true;
      }
    }
    if (swaped) {
      break;
    }
  }
}

num = [2, 4, 1, 5, 7, 6, 9, 8];
// 快速排序
// 合法的下标是从begin到end-1，不包含end
function quick(a, begin, end) {
  if (begin >= end - 1) {
    return;
  }

  //使用a[begin]将其分为两个部分，[begin, j) 和[j+1, end)
  // 左边的都比j小，右边的都比j大
  let j = end - 1;
  let i = begin + 1;
  while (i <= j) {
    // 找出一个i使得 a[i] > a[begin]
    while (i < end && a[i] <= a[begin]) {
      i++;
    }
    // 找出一个j使得 a[j] <= a[begin]
    while (a[j] > a[begin]) {
      j--;
    }
    // 交换i和j
    if (i < j) {
      swap(a, i, j);
      i++;
      j--;
    }
  }

  // 交换a[j] 和 a[begin]
  if (begin != j) {
    swap(a, begin, j);
  }

  // 对左边的数组再次排序
  quick(a, begin, j);
  // 对右边的数组再次排序
  quick(a, j + 1, end);
}

function quickSort(a) {
  quick(a, 0, a.length);
}

module.exports = {
  sort: bubble,
};


// 归并排序
function mergeSort(a,begin,end){
    if(begin>=end-1){
        return;
    }
    // 表示中间为元素的下标
    let middle = Math.floor(begin + end) / 2;
    mergeSort(a,begin,end);
    mergeSort(a,middle,end);
    mergeSort(a,begin,middle,end);
}